package com.syxbyi.yudong.class01;

import java.util.Arrays;

public class PlusOne {

    public static int[] plusOne(int[] digits) {
        if (digits == null || digits.length == 0) {
            return null;
        }
        int N = digits.length;
        int[] res;
        // 从后往前数有几个连续的 9，就能确定改动最多影响到哪个位置
        int count9 = 0;
        while (count9 != N && digits[N - count9 - 1] == 9) {
            count9++;
        }
        // 举例，[1, 2, 3, 4, 5, 9, 9, 9], count9 = 3, N = 8
        // index 0  1  2  3  4  5  6  7
        // 第一个 9 的下标是 N - count9，而最远的受影响位置 5 的下标是 N - count9 - 1
        if (count9 == N) {              // digits 数组全是 9，所以加 1 之后多一位
            res = new int[N + 1];
            res[0] = 1;
        } else {
            res = new int[N];
            int i = 0;
            // 直接复制 [0, N - count9 - 1]，[0, N - count9 - 2] 不变
            // N - count9 - 1 是最早的不是 9 的位置，直接加一即可，后面都是 0
            // count9 = 0 时也成立
            for (; i < N - count9; i++) {
                res[i] = digits[i];
            }
            res[i - 1]++;               // 此时 i = N - count9 - 1
        }
        return res;
    }

}
